%----------------------
%      整除
%----------------------

%\chapter{整除}


\section{整除与带余除法}
我们通常用$\mathbb{N}$表示正整数（自然数）集合，用$\mathbb{Z}$表示整数集合。
\begin{definition}{整除(to be divisible by)}{int}
	$a,b \in \mathbb{Z},b \neq 0$,如果存在$q \in \mathbb{Z}$,使得$a=qb$,就称a可被b整除或者b整除a，记为$b\mid a$。
	a是b的倍数(multiple)，b是a的因子(factor)（或约数、除数）(divisor)。若a不能被b整除，记为$b \nmid a$。
\end{definition}
\begin{remark}
	给定两个数，如何判断是否是整除关系？也就是说，判断整除的算法是什么？
\end{remark}
\begin{definition}{真因子(proper factor)}{int}
	$b \mid a,b\neq \pm 1 ,b \neq \pm a,$,称b为a的真因子。
\end{definition}

\begin{theorem}{整除定理}{set}
	$a,b,c \in \mathbb{Z}$
	\begin{enumerate}
		\item  $b \mid a \Leftrightarrow -b \mid a \Leftrightarrow b \mid -a \Leftrightarrow \left| b \right| \mid \left| a \right|$；
		\item  $a \neq 0,b \mid a \Rightarrow \left| b \right| \leq \left| a \right|$;
		\item  $b \mid a,c \mid b \Rightarrow c \mid a$；
		\item  $b \mid a \Rightarrow b \mid ac$;
		\item  $c \neq 0,b \mid a \Leftrightarrow bc \mid ac$;
		\item  $b \mid a, b \mid c \Leftrightarrow m,n \in \mathbb{Z},b \mid ma+nc$;
	\end{enumerate}
\end{theorem}

\begin{theorem}{良序原理(公理)(well ordering principle)}{set}
	每一个由非负整数组成的非空集合$\mathbb{S}$必定含有一个最小元素。
\end{theorem}
良序原理与我们的直观感觉相同，但是这个原理无法证明，所以良序原理是一个公理。

\begin{theorem}{带余除法(division alogorithm)}{set}
	$a,b \in \mathbb{Z},b > 0$，则存在唯一的一对整数q和r，使$a = qb + r \left( 0 \leq r < b \right)$。
	其中a称为被除数(dividend)，q称为商(quotient)，r称为余数(remainder)。
\end{theorem}

\begin{definition}{奇数(odd number)，偶数(even number)}{int}
	$a,b,r \in \mathbb{Z},a=2q+r, 0 \leq r < 2$,若$r = 0$,称a为偶数，若$r=1$，称a为奇数。
\end{definition}

\begin{definition}{素数(prime)，合数(composite number)}{int}
	$p \in \mathbb{Z},p > 1$,如果p的真因子只有1和其自身，称p为素数（或质数）。除1以外所有非素数的正整数称为合数（或复合数）。
\end{definition}

\begin{theorem}{无穷素数}{set}
	素数有无穷多个。
\end{theorem}
\begin{proof}(欧几里德证明\footnote{公元前300年左右，古希腊数学家欧几里德写在《几何原本》中的一个古老定理（欧几里德定理）和它的证明，距今已有两千多年的历史了。(来自于数学科普微信公众号“职业数学家在民间”(微信号：minjianshuxuejia)，其中的一片文章“【人人都能欣赏的数学证明】为什么有无限多个素数？”)})\par
	用反证法，假定只有有限个素数$p_1,p_2,\ldots,p_k$，设$a= p_1 p_2 \ldots p_k +1 $，由于a是合数，所以a必有素因子，不失一般性，假设这个素因子是$p_j (1 \leq j \leq k)$,显然$p_j \mid a$,因为$a-p_1 p_2 \ldots p_k =1$,同时$p_j \mid (p_1 p_2 \ldots p_k)$,故$p_j \mid  1$，但是因为素数$p_j \geq  2$,与$p_j \mid  1$矛盾，故假定错误，定理得证。
\end{proof}

\begin{theorem}{素数性质}{set}
	\begin{itemize}
		\item $n \in \mathbb{N}$，存在素数p，满足$ n < p \leq  n!+1 $。
		\item $n \in \mathbb{Z},n \geq 2\Rightarrow$ $n!+2$与$n!+n$之间必没有素数 。
		\item n为合数 $\Rightarrow$ n必有素数因子p满足$p \leq \sqrt{n}$ 。
		\item 若$2^n -1$为素数，则n必为素数。
	\end{itemize}
	
\end{theorem}


\begin{example}
	证明：n为合数 $\Rightarrow$ n必有素数因子p满足$p \leq \sqrt{n}$ 。
\end{example}
\begin{proof}
	设p为n的最小素因子，如果$n=r\cdot s$,r和s均为n的真因子，那么$p \leq r \wedge p \leq s$,所以$p^2 \leq r \cdot s = n, p \leq \sqrt{n}$
\end{proof}

\begin{example}\\
	质数判断用2到$\sqrt{n}$之间的所有整数去除正整数n，均无法整数，则n为质数，这也是通常编程判断一个数是否为质数的方法。
\end{example}

\begin{example}
	证明：若$2^n -1$为素数，则n必为素数。
\end{example}
\begin{proof}
	对于n>1,假设n为合数，n=bc，b和c均为大于1的整数，则$2^b -1 \mid 2^n -1$,所以$2^n -1$为合数，这与条件相矛盾。
\end{proof}

\begin{remark}
	(1)如何判断一个数是否为素数？也就是通常说的素性判定。\par
	(2)目前常用的素性判断方法是Miller-Rabin算法。
\end{remark}

\textbf{The Sieve of Eratosthenes}\footnote{cited from https://www.smartickmethod.com/blog/math/operations-and-algebraic-thinking/divisibility/prime-numbers-sieve-eratosthenes/ ,在这个网页内有以动画方式表示的筛选过程，可以参考阅读，来理解此算法}\par
The Greek mathematician Eratosthenes (3rd-century B.C.E) designed a quick way to find all the prime numbers. It’s a process called the Sieve of Eratosthenes. We’re going to see how it works by finding all the prime numbers between 1 and 100.
The idea is to find numbers in the table that are multiples of a number and therefore composite, to discard them as prime. The numbers that are left will be prime numbers.
The Sieve of Eratosthenes stops when the square of the number we are testing is greater than the last number on the grid (in our case 100).
Since 112  = 121 and 121>100, when we get to the number 11, we can stop looking.

\section{最大公因子}

\subsection{基本概念}

\begin{definition}{公因子(common factor),最大公因子(greatest common factor),互素(relatively prime)}{int}
	设$a_1,a_2, \ldots a_n$是n个不全为零的整数,若整数d是他们之中每一个数的因子，那么d就称为$a_1,a_2, \ldots a_n$的一个公因子，所有公因子中最大的称为最大公因子，记为$gcd(a_1,a_2, \ldots a_n)$。若$gcd(a_1,a_2, \ldots a_n)=1$，称$a_1,a_2, \ldots a_n$互素（或互质）。
\end{definition}

\subsection{性质}

\begin{theorem}{最大公因子性质}{set}
	\begin{itemize}
		\item a,b,c是任意三个不全为零的整数，且$a = bq+c$，q是整数$\Rightarrow$ $gcd(a,b)=gcd(b,c)$。
		\item 对于任意两个整数a和b，一定存在两个整数m和n，使得$gcd(a,b)=ma+nb$,也就是说$gcd(a,b)$是a和b的整系数线性组合。
		\item $a,b,c \in \mathbb{Z},c \mid a \wedge c \mid b \Rightarrow c \mid gcd(a,b)$.
		\item $a,b,c \in \mathbb{Z},c > 0 \Rightarrow gcd(ac,bc)= gcd(a,b) \times c$.
		\item $a,b,c \in \mathbb{Z},a \mid bc \wedge gcd(a,b)=1 \Rightarrow a \mid c$.
		\item $a_1,a_2,\ldots,a_n \in \mathbb{Z},gcd(a_1,a_2)=d_2,gcd(d_2,a_3)=d_3,\ldots,gcd(d_{n-1},a_n)=d_n \Rightarrow gcd(a_1,a_2,\ldots,a_n)=d_n$.
	\end{itemize}
\end{theorem}
\begin{example}
	证明上面的性质：a,b,c是任意三个不全为零的整数，且$a = bq+c$，q是整数$\Rightarrow$ $gcd(a,b)=gcd(b,c)$。
\end{example}
\begin{proof}
	$gcd(a,b) \mid a , gcd(a,b) \mid b ,c=a-bq \Rightarrow gcd(a,b)|c$\\
	所以，$gcd(a,b)$是b和c的公因子\\
	那么有，$gcd(a,b) \leq gcd(b,c)$。\\
	\begin{equation*}
		\left.\begin{aligned}
			a=bq+c \Rightarrow gcd(b,c) \mid a\\
			gcd(b,c) \mid b
		\end{aligned} \right \}  \Rightarrow gcd(b,c) \leq gcd(a,b)
	\end{equation*}
由上可知$gcd(a,b)=gcd(b,c)$.
\end{proof}
\begin{example}
	已知$35=10 \times 3 +5$,可知$gcd(35,10)=5,gcd(10,5)=5$.
\end{example}
\begin{example}
	已知$529=130 \times 4 + 9$
\end{example}
\begin{solution}
	我们先用sagemath计算一下：
	\begin{SageMath}{求两数最大公约数}
		\begin{verbatim}
			sage: gcd(529,130)
			1
			sage: gcd(130,9)
			1
			sage:
		\end{verbatim}
	\end{SageMath}
	然后手工计算一下：\par
	$529=130 \times 4+9,gcd(529,130)=gcd(130,9)$\par
	$130=9 \times 14 + 4,gcd(130,9)=gcd(9,4)$\par
	$9=4 \times 2 + 1,gcd(9,4)= gcd(4,1)$\par
	$4=1 \times 4 +0,gcd(4,1)=1$\par
	所以，529、130互质。
\end{solution}

\subsection{欧几里得除法}

给定任意两个正整数a和b(任意两个整数呢？)，假设$a \geqslant b$，如何求解a和b的最大公因数呢？
\begin{tcolorbox}[title = {辗转相除法/欧几里得除法(Euclid's algorithm)}]
	求a,b最大公因数的方法(设$a \geq b$)
	\tcblower
	$
		a=bq_1+r_1,0<r_1<b\\
		b=r_1q_2+r_2,0<r_2<r_1\\
		r_1=r_2q_3+r_3,0<r_3<r_2\\
		\ldots \\
		r_{n-1}=r_n q_{n+1}+r_{n+1},r_{n+1}=0.\\
		gcd(a,b)=r_n
	$
\end{tcolorbox}
\begin{example}\\
	a=1560,b=1200，求a,b的最大公因子。
\end{example}
\begin{solution}
	 $
	 	1560=1200 \times 1 + 360 \newline
	 	1200=360 \times 3 +120 \newline
	 	360=120 \times 3 +0 \\
	 	gcd(1560,1200)=120
	 $\\
	 为了使得过程更加清晰，我们做一张表，展示其过程,初始$q_0=a=1560,r_0=b=1200$：\\
	 \begin{tabular}{|c|c|c|c|c|}
	 	\hline 
	 	i & $q_i$ & $r_i$ & $m_i$  & $r_{i+1}$ \\ 
	 	\hline 
	 	0 & 1560 & 1200 & 1  & 360 \\ 
	 	\hline 
	 	1 & 1200 & 360 & 3 & 120 \\ 
	 	\hline 
	 	2 & 360 & 120 & 3 & 0  \\ 
	 	\hline 
	
	 \end{tabular} 
\end{solution}
\begin{theorem}{最大公因子性质}{set}
	\begin{itemize}
		\item 任给两个正整数a和b, 一定存在两个整数m,n, 使得$gcd(a,b)=ma+nb$，即gcd(a,b)是a和b的线性组合.
		\item 设整数a,b,c满足$c\mid a \wedge c\mid b$, 则$c \mid gcd(a,b)$.
		\item $a,b,c \in \mathbb{Z},c > 0 \Rightarrow gcd(ac,bc) = gcd(a,b)c$.
		\item 整数a,b互素的充分必要条件是存在整数x,y, 使得$xa+yb=1$.
		\item 设有整数a,b,c, 若$a \mid bc$且$gcd(a,b) = 1$, 则$a \mid c$.
		\item 设$a_1,a_2,…,a_n \in \mathbb{Z}$, 其中$a_1 \neq 0$. 令
		$gcd(a_1,a_2 )=d_2,gcd(d_2 a_3 )=d_3,…,gcd(d_{n−1},a_n )=d_n \Rightarrow gcd(a_1,a_2,…,a_n )=d_n$.
	\end{itemize}
\end{theorem}
\section{最小公倍数}

\subsection{基本概念}

\begin{definition}{最小公倍数(least common multiple)}{int}
	设$a_1,a_2,…,a_n$是n个整数, 若m是这n个数中每一个数的倍数, 则m就称为这n个数的一个公倍数. 在$a_1,a_2,…,a_n$的所有公倍数中最小的正整数称为最小公倍数, 记作$\left[ a_1,a_2,…,a_n\right] $或者$lcm(a_1,a_2,…,a_n)$.
\end{definition}
已知最小公倍数的定义，如何来求解最小公倍数，下面我们进行简单的讨论。
\begin{theorem}{互素数的最小公倍数}{set}
	设a和b为任意两个互素正整数, 则其乘积即为最小公倍数。
\end{theorem}

\begin{example}\\
	5和7的最小公倍数是$5 \times 7 = 35$,4和8的最小公倍数数是8，而不是$4 \times 8 = 32$.
\end{example}

\subsection{性质}

\begin{theorem}{最小公倍数性质}{set}
	设a和b为任意正整数, 则\\
	(1) 若m是a,b的任一公倍数, 则$lcm(a,b) \mid m$；\\
	(2) $lcm(a,b)=\frac{ab}{gcd(a,b)}$.\\
	(3)	$gcd(a,b)\times lcm(a,b) = a\times b$
\end{theorem}

\begin{example}\\
	4和8的最大公约数为4，所以$lcm(4,8)=\frac{4 \times 8}{4}$
\end{example}

\begin{theorem}{最小公倍数性质}
	设$a_1,a_2,…,a_n$是n个整数, \\
	\begin{itemize}
		\item  $lcm(a_1,a_2)=m_2,lcm(m_2,a_3) =m_3,…,lcm(m_(n−1),a_n)=m_n \Rightarrow	lcm(a_1,a_2,…,a_n)=m_n$.
		\item  $a_1 \mid m, a_2 \mid m,…, a_n \mid m \Rightarrow lcm(a_1,a_2,...,a_n) \mid m$.
	\end{itemize}
\end{theorem}

由上面的定理我们可以得出，对于一组整数，求其最小公倍数时，可以转换为求解一系列两两之数的最小公倍数。
也就是我们可以利用两个数最小公倍数的算法做为运算单元，求解多个数的最小公倍数。

\section{算术基本定理}
\subsection{算术基本定理}
\begin{theorem}{算术基本定理(Fundamental Theorem of arithmetric)}{int}
	任一大于1的整数都可以表示成素数的乘积, 且在不考虑乘积顺序的情况下, 该表达式是唯一的. 即$n=p_1 p_2\ldots p_s,p_1\leq p_2 \leq \ldots \leq p_s$,
	其中$p_1 p_2\ldots p_s$是素数, 并且若
	$n=q_1 q_2\ldots q_t,q_1\leq q_2 \leq \ldots \leq q_t$,
	其中$q_1 q_2\ldots q_t$是素数, 则$s=t,p_i = q_i (i=1,2,\ldots ,s)$.
\end{theorem}

算术基本定理也被称为整数的唯一分解定理。

\begin{theorem}{标准分解式}{int}
	任一大于1的整数都能够唯一地表示成$n=p_1^{a_1} p_2^{a_2} \ldots p_s^{a_s},a_i>0,i=1,2,\ldots,s$，其中$p_i<p_j(i<j)$是素数。
\end{theorem}
\subsection{整数分解方法}
给定一个整数，计算此整数的分解式的一般方法是，用小于此整数的素数，从大到小，去除此数，能整除，则此素数是一个素因子，然后继续用此方法找商的第一个素因子，依次类推。\par
\begin{example}\\
	计算360的唯一分解。
\end{example}
\begin{solution}
	$360=2^3 \times 3^2 \times 5$
\end{solution}

\begin{example}\\
	大数分解6596783,6596784。
\end{example}
\begin{solution}
	\begin{SageMath}{整数分解}
		\begin{verbatim}
		sage: factor(6596783)
		6596783
		sage: factor(6596784)
		2^4 * 3^2 * 61 * 751
		sage:
		\end{verbatim}
	\end{SageMath}
\end{solution}
\begin{note}\par
	(1)素数表。做整数分解，最直观的方法就是依次用素数去除，可以整除就是其一个因子，可见先有一张素数表很重要，那么怎么来准备这张素数表呢？\par
	(2)大数运算。编程语言通常的数的范围有限，所以通常在进行密码学上的计算或者一些数据计算时，需要有大数运算能力，这需要专有运算库来支持。\par
	(3)C语言int占2 bytes，符号位占一位，正数最大为$2^15 = 32768$\par
	(4)开源项目GMP(GNU multiple precision arithmetic library),网站https://gmplib.org/
\end{note}

\subsection{标准分解式的应用}
\begin{theorem}{正因子个数}{int}
	设正整数n的标准分解式为$n=p_1^{a_1} p_2^{a_2} \ldots p_s^{a_s},a_i \ge 0,i =1,2,\ldots , s,\tau (n)$表示n的所有正因子的个数，则$\tau (n) = \tau (p_1^{a_1})  \tau (p_2^{a_2}) \tau (p_s^{a_s})=(a_1 +1 )(a_2 +1 )\ldots(a_s +1 )$	
\end{theorem}

\begin{example}
	$84=2^2 \times 3 \times 7$,求$\tau(84)$
\end{example}
\begin{solution}
	$\tau(84)=(2+1)(1+1)(1+1)=12$，也就是说84共有12个正因子，下面我们罗列一下这12个正因子：\\
	1,84,2,3,4,6,7,12,14,21,28,42.
\end{solution}
\begin{example}\\
	计算360的所有正因子的个数。
\end{example}
\begin{solution}
	$360=2^3 \times 3^2 \times 5, \tau (360)= \tau (2^3) \tau (3^2) \tau (5)=(3+1)(2+1)(1+1)=24$
\end{solution}

\begin{theorem}{int}
	整数a和b的整数分解式为：\\
	$
	a=p_1^{\alpha_1}p_2^{\alpha_2}\ldots p_s^{\alpha_s},\alpha_i >0,i=1,2,\ldots,s\\
	b=p_1^{\beta_1}p_2^{\beta_1}\ldots p_s^{\beta_s},\beta_i >0,i=1,2,\ldots,s\\
	$
	那么：\\
	$gcd(a,b)=p_1^{\gamma_1}p_2^{\gamma_2}\ldots  p_s^{\gamma_s},\gamma_i = min(\alpha_i,\beta_i),i=1,2,\ldots,s.\\
	lcm(a,b)=p_1^{\delta_1}p_2^{\delta_2}\ldots  p_s^{\delta_s},\delta_i = max(\alpha_i,\beta_i),i=1,2,\ldots,s.\\
	$
\end{theorem}



\section{完全数、梅森素数和费马素数}

\begin{theorem}{完全数}{int}
	若正整数n的所有正因子之和等于2n，则n称为完全数。
\end{theorem}

\begin{example}\\
	6的正因子有1、2、3、6，$1+2+3+6=12,2 \times 6 =12$，根据完全数定义，6是一个完全数。
\end{example}


我们用$\sigma(n)$表示正整数n的所有正因子之和，所以如果n是完全数，那么$\sigma(n) = 2n$。\par
完全数（Perfect number），又称完美数或完备数，是一些特殊的自然数。它所有的真因子（即除了自身以外的约数）的和（即因子函数），恰好等于它本身。例如：第一个完全数是6，它有约数1、2、3、6，除去它本身6外，其余3个数相加，1+2+3=6。第二个完全数是28，它有约数1、2、4、7、14、28，除去它本身28外，其余5个数相加，1+2+4+7+14=28。第三个完全数是496，有约数1、2、4、8、16、31、62、124、248、496，除去其本身496外，其余9个数相加，1+2+4+8+16+31+62+124+248=496。后面的完全数还有8128、33550336等等。\par

公元前6世纪的毕达哥拉斯是最早研究完全数的人，他已经知道6和28是完全数。毕达哥拉斯曾说：“6象征着完满的婚姻以及健康和美丽，因为它的部分是完整的，并且其和等于自身。”有些《圣经》注释家认为6和28是上帝创造世界时所用的基本数字，因为上帝创造世界花了六天，二十八天则是月亮绕地球一周的日数。圣·奥古斯丁说：6这个数本身就是完全的，并不因为上帝造物用了六天；事实上，因为这个数是一个完全数，所以上帝在六天之内把一切事物都造好了。\par
在中国文化里：有六谷、六畜、战国时期的六国、秦始皇以六为国数、六常（仁、义、礼、智、信、孝）、天上四方有二十八宿等等，6和28，在中国历史长河中，之所以熠熠生辉，是因为它是一个完全数。难怪有的学者说，中国发现完全数比西方还早呢。\par
完全数诞生后，吸引着众多数学家与业余爱好者像淘金一样去寻找。它很久以来就一直对数学家和业余爱好者有着一种特别的吸引力，他们没完没了地找寻这一类数字。接下去的两个完数看来是公元1世纪，毕达哥拉斯学派成员尼克马修斯发现的，他在其《数论》一书中有一段话如下：也许是这样，正如美的、卓绝的东西是罕有的，是容易计数的，而丑的、坏的东西却滋蔓不已；是以盈数和亏数非常之多，杂乱无章，它们的发现也毫无系统。但是完全数则易于计数，而且又顺理成章：因为在个位数里只有一个6；十位数里也只有一个28；第三个在百位数的深处，是496；第四个却在千位数的尾巴颈部上，是8128。它们具有一致的特性：尾数都是6或8，而且永远是偶数。但在茫茫数海中，第五个完全数要大得多，居然藏在千万位数的深处！它是33550336，它的寻求之路也更加扑朔迷离，直到十五世纪才由一位无名氏给出。这一寻找完全数的努力从来没有停止。电子计算机问世后，人们借助这一有力的工具继续探索。笛卡尔曾公开预言：“能找出完全数是不会多的，好比人类一样，要找一个完美人亦非易事。”时至今日，人们一直没有发现有奇完全数的存在。于是是否存在奇完全数成为数论中的一大难题。只知道即便有，这个数也是非常之大，并且需要满足一系列苛刻的条件。\footnote{https://baike.baidu.com/item/完全数}

\begin{theorem}{梅森数(Mersenne number)}{int}
	p是一个素数，形如$2^p-1$的数叫做梅森数，记作$M_p = 2^p -1$，当$M_p$是素数时，则称其为梅森素数。
\end{theorem}	

古希腊数学家欧几里得在名著《几何原本》中证明了素数有无穷
多个，并论述完全数时提出：如果$2^P-1$是素数(其中指数P也是素数)，则$2^(P-1)(2^P-1)$是完全数。瑞士数学家和物理学家欧拉证明所有的偶完全数都有这种形式。因此，人们只要找到$2^P-1$型素数，就可以发现偶完全数了。数学界将$2^P-1$型素数称为“梅森素数”(Mersenne prime)，因为法国数学家和法兰西科学院奠基人梅森在这方面的研究成果较为卓著。梅森素数貌似简单，但探究难度却极大。它不仅需要高深的理论和纯熟的技巧，而且还需要进行艰巨的计算。到2013年2月6日为止，人类仅发现48个梅森素数。
值得提出的是：在梅森素数的基础研究方面，法国数学家鲁卡斯和美国数学家雷默都做出了重要贡献；以他们命名的“鲁卡斯-雷默方法”(Lucas-Lehmer primality test)是目前已知的检测梅森素数素性的最佳方法。此外，中国数学家和语言学家周海中给出了梅森素数分布的精确表达式，为人们寻找梅森素数提供了方便；这一研究成果被国际上命名为“周氏猜测”。\par

美国中央密苏里大学数学家库珀领导的研究小组通过参加一个名为“互联网梅森素数大搜索”(GIMPS)\footnote{GIMPS是great internet Mersenne Prime search,网站在www.mersenne.org}项目，于2016年1月7日发现了第49个梅森素数——$2^{74207281}-1$。该素数也是目前已知的最大素数，有22,338,618位。这是库珀教授第四次通过GIMPS项目发现新的梅森素数，刷新了他的记录。他上次发现第48个梅森素数$2^{57885161}-1$是在2013年1月，有17425170位。\par
梅森素数在当代具有重大意义和实用价值。它是发现已知最大素数的最有效途径，其探究推动了“数学皇后”——数论的研究，促进了计算技术、密码技术、程序设计技术和计算机检测技术的发展。难怪许多科学家认为，梅森素数的研究成果，在一定程度上反映了一个国家的科技水平。英国数学协会主席马科斯 索托伊甚至认为它的研究进展不但是人类智力发展在数学上的一种标志，也是整个科技发展的里程碑之一。\par
所有的奇素数都是准梅森数$（2^N-1）$的因 子数，凡是一个素数是四倍金字塔数A的因子数，都不是以后梅森合数的因子数，则留下部份素数可能都是梅森合数的因子数。



\begin{theorem}{费马数(Fermat number)}{int}
	n是非负整数，则$F_n = 2^{2^n}+1$称为费马数。当$F_n$为素数时，称其为费马素数。
\end{theorem}

法国数学家费马于1640年提出了以下猜想:\par
$F_0 , F_1 , F_2 , F_3 , F_4$都是质数，因为第六个数实在太大，费马没有计算出来，他猜测第六个数也是素数。由此提出费马数都是素数的猜想。\par
1732年，欧拉算出$F_5=641 \times 6700417$，也就是说$F_5$不是质数，宣布了费马的这个猜想不成立，它不能作为一个求质数的公式。以后，人们又陆续找到了不少反例，如n=6 时，$F6=2^{2^6} +1  =274177×67280421310721$不是质数。至今这样的反例共找到了243个，却还没有找到第6个正面的例子，也就是说只有n=0，1，2，3，4这5个情况下，$F_n$才是质数。
